package test.n00100;


import java.util.Arrays;

public class Problem00160 {
    public static void main(String[] args) {
        println(new int[]{-1, 2, 1, -4}, 1);
        println(new int[]{0, 0, 0}, 1);
    }

    public static void println(int[] nums, int target) {
        Solution ss = new Solution();
        System.out.println(Arrays.asList(nums) + "," + ss.threeSumClosest(nums, target));
    }

    public static class Solution {

        /**
         * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
         * <p>
         * 返回这三个数的和。
         * <p>
         * 假定每组输入只存在恰好一个解。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/3sum-closest
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 解题思路:
         * 排序+双指针
         *
         * @param nums
         * @param target
         * @return
         */
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);

            int len = nums.length;
            int best = 10000000;

            for (int i = 0; i < len; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }

                int left = i + 1;
                int right = len - 1;
                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum == target) {
                        return target;
                    }

                    if (Math.abs(sum - target) < Math.abs(best - target)) {
                        best = sum;
                    }

                    if (sum > target) {
                        // 如果和大于 target，移动 c 对应的指针
                        int right0 = right - 1;
                        // 移动到下一个不相等的元素
                        while (left < right0 && nums[right0] == nums[right]) {
                            --right0;
                        }
                        right = right0;
                    } else {
                        // 如果和小于 target，移动 b 对应的指针
                        int left0 = left + 1;
                        // 移动到下一个不相等的元素
                        while (left0 < right && nums[left0] == nums[left]) {
                            ++left0;
                        }
                        left = left0;
                    }
                }
            }
            return best;
        }
    }
}
